#!/usr/bin/env python3

"""
Combination Sum
"""

class Solution:
    def combination_sum(self, candidates, target):
        result = []
        for case in self._combination_sum(candidates, target, 0):
            if case is not None:
                result.append(case)
        return result


    def _combination_sum(self, candidates, target, start):
        candidates.sort()
        first = candidates[start]
        quotient = int(target / first)
        if quotient == 0:
            return
        for first_times in range(quotient, -1, -1):
            remain = target - first_times * first
            if remain == 0:
                yield [first] * first_times
            elif start == len(candidates) - 1:
                yield None
            else:
                for result in self._combination_sum(candidates, remain, start + 1):
                    if result is None:
                        continue
                    for index in range(first_times):
                        result.insert(0, first)
                    yield result

if __name__ == '__main__':
    solution = Solution()
    result = solution.combination_sum([8, 7, 4, 3], 11)
    print(str(result))
